CF1223E Paint the Tree

锻炼了转化题意的能力

题解：

首先转化题意：题目告诉你一个点最多k种颜色，每种颜色最多两次，两端点同色边能获得它的贡献

显然的，同色获贡献，换句话说，就是如果想要某条边的贡献的话，就要将它们涂上同一种颜色，也就是说，一个点最多选k条相连边的贡献

此时，题意变为选若干条边，规定每个点的边集中最多选k条，问最大边权和

问最大价值，肯定要用贪心，但在这里只能是个局部贪心，即在每在所有相连边里，在满足规定的前提下，尽可能选大边

注意到一个点连出的会有两种边，父边和子边，如果不选父边的话，就可以在子边里贪心选k条，否则就只能选k-1条（即减去第k大的子边）

于是设$f[x][1/0]$表示以x为根的子树内的最大边权和，1表示选父边，0表示不选

需要注意的是，对于$f[x][1]$是并不包括父边贡献的，因为对它的定义是以x为根的子树内的最大边权和，搞清楚设的是什么，这很重要

对于转移，$f[x][0]$就是累加子边里最大的k个价值，而$f[x][1]$是k-1个

具体的，子边的价值是指$\max(f[son][0],f[son][1]+w[x][son])$

另外在代码中还有许多巧妙的小细节，有助于精简代码

如先将$f[x][1]$看成$f[x][0]$一起处理，最后再减去第k大的子边贡献

又如先假设都不选子边，累加上$f[son][0]$，经对$f[son][1]+w[x][son]-f[son][0]$进行排序，最后如果排序出来的前k个是正数（即选子边更优）的话，就也累加上，更新最优值，这个最优值就是$f[x][0]$

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

#define int long long

const int N=5e5+5;
int en,h[N],n,k,f[N][2];

struct edge{
    int n,v,w;
}e[N<<1];

void add(int x,int y,int z){
    e[++en]=(edge){h[x],y,z};
    h[x]=en;
}

void dfs(int x,int fa){
    int tot=0;
    vector<int> a;
    for(int i=h[x];i;i=e[i].n){
        int y=e[i].v;
        if(y==fa) continue;
        dfs(y,x);
        tot+=f[y][0]; //假设都不选子边
        a.push_back(f[y][1]+e[i].w-f[y][0]);
    }
    sort(a.begin(),a.end(),greater<int>());
    for(int i=0;i<min((int)a.size(),k);i++) if(a[i]>0) tot+=a[i]; //拿差值更新最优值
    f[x][0]=f[x][1]=tot;
    if(k<=a.size()&&a[k-1]>0) f[x][1]-=a[k-1]; //除去第k大的，留给父边
}

void doit(){
    read(n);read(k);
    for(int i=1;i<=n;i++) h[i]=0;
    en=0;
    for(int i=1,x,y,z;i<n;i++){
        read(x);read(y);read(z);
        add(x,y,z);
        add(y,x,z);
    }
    dfs(1,0);
    write(f[1][0]);puts("");
}

signed main(){
    int t;
    read(t);
    while(t--) doit();
}